import java.util.Random;
import java.util.Vector;

public class IAPrac1State 
{
	public static int MAX_PLAZASO = 2;    // El usuario conductor siempre ocupa una plaza
    public static int MAX_HMSREC  = 300;  // Distancia maxima: 1h * 30km/h * 10hm/1km
    public static int CITY_SIZE   = 100;  // Height/Width of the city
    public static int NUM_COORD   = 4;    // Numero de coordenadas de las posiciones de los usuarios
    public static String ASIGNAR      = "Asignar";
    public static String MOVER        = "Mover";
    public static String INTERCAMBIAR_CONTIGUOS = "Intercambiar pasajeros contiguos";
    public static String INTERCAMBIAR = "Intercambiar";
    public static String CREAR_CONDUCTOR = "Crear conductor";
    public static String ELIMINAR_CONDUCTOR = "Eliminar conductor";
    public static String ELIMINAR_PASAJERO = "Eliminar pasajero";
    
    public static int N; // Numero de Usuarios del sistema
    public static int K; // Numero de Usuarios que pueden conducir
    
    public static int[][] registro;
    private Vector<Vector<Integer>> conductores;
    public int ncond; // Numero de conductores actuales
    private Vector<Integer> pasajerosPendientes;
    public int npas; // Numero de pasajeros pendientes actuales
    
    // Constructoras
	public IAPrac1State(int N, int M) {
    	IAPrac1State.N = N;
    	IAPrac1State.K = N - M;
    	
    	registro = new int[N][NUM_COORD];
    	Random rand = new Random();
    	
    	// Generacion aleatoria de usuarios
    	for (int i = 0; i < N; i++) {
    		// Generacion aleatoria de la posicion inicial
    		registro[i][0] = rand.nextInt(CITY_SIZE); // xini
    		registro[i][1] = rand.nextInt(CITY_SIZE); // yini
    		registro[i][2] = rand.nextInt(CITY_SIZE); // xfin
    		registro[i][3] = rand.nextInt(CITY_SIZE); // yfin
    		
    		// Aseguramos que las posiciones de origen y destino son distintas
    		while(registro[i][0] == registro[i][2] && registro[i][1] == registro[i][3]) {
    			registro[i][2] = rand.nextInt(CITY_SIZE);
    			registro[i][3] = rand.nextInt(CITY_SIZE);
    		}
    	}
    	
    	// Inicialmente no hay ningun conductorr
    	ncond = 0;
    	conductores = new Vector<Vector<Integer>>();
    	
    	// Inicialmente todos los usuarios son pasajeros
    	npas = N;
    	pasajerosPendientes = new Vector<Integer>();
    	for (int i = 0; i < N; i++) pasajerosPendientes.add(i);
    }
    
	public IAPrac1State(Vector<Vector<Integer>> conds, int numcond, Vector<Integer> pasPends, int numpas) {
    	ncond = numcond;
		conductores = copiaConductores(conds);
    	npas = numpas;
    	pasajerosPendientes = copiavectorInteger(pasPends);
    }
    
    
    // Generacion estado inicial    
    public void IAPracStateSolucionInicialA() {	
    	// Todos los Usuarios que pueden conducir pasan a ser conductores    	
    	ncond = K;
        for (int i = 0; i < K; i++) {
    		conductores.add(new Vector<Integer>());
    		pasajerosPendientes.removeElement(i);
    		npas--;
    	}

    	// Asignacion rotativa de pasajeros a los conductores mientras haya
    	// pasajerosPendientes o no se puedan asignar
    	int con = 0;
    	int nfallos = 0;
    	boolean asignado = false;
    	
    	while (nfallos < N) {
    		// Podemos asignar
    		for (int pas = 0; pas < N && !asignado; pas++)	
        		if (pasajerosPendientes.contains(pas) && asignarPasajero(con, pas)) {
        			asignado = true;
        		}
	    		
	    	if (!asignado) nfallos++;
    		else nfallos = 0;

    		con = (con + 1)%K;
    		asignado = false;
    	}
    	
    	// Los conductores que no poseen ningun pasajero asignado dejan de serlo
    	for (int i = 0; i < K; i++)	{
    		if (((Vector<Integer>)conductores.get(i)).isEmpty()) {
    			eliminarConductor(i);
    		}
    	}
    }

    public void IAPracStateSolucionInicialA1() {	
    	// Todos los Usuarios que puedenConducir pasan a ser Conductores
    	ncond = K;
    	for (int i = 0; i < K; i++) {
    		conductores.add(new Vector<Integer>());
    		pasajerosPendientes.removeElement(i);
    		npas--;
    	}
    	
    	// Asignacion rotativa de pasajeros a los conductores mientras haya
    	// pasajerosPendientes o no se puedan asignar
    	int con = 0;
    	int nfallos = 0;
    	boolean asignado = false;
    	
    	while ((nfallos < N) /*&& (npas > (N - K)/2)*/) {
    		// Podemos asignar
    		for (int pas = 0; pas < N && !asignado; pas++)	
    			if (pasajerosPendientes.contains(pas) && asignarPasajero(con, pas)) {
        			asignado = true;
        		}
	    		
	    	if (!asignado) nfallos++;
    		else nfallos = 0;

    		con = (con + 1)%K;
    		asignado = false;
    	}
    }
    
    public void IAPracStateSolucionInicialB() {	
    	
    	// Todos los Usuarios que puedenConducir pasan a ser Conductores
    	ncond = K;
    	for (int i = 0; i < K; i++) {
    		conductores.add(new Vector<Integer>());
    		pasajerosPendientes.removeElement(i);
    		npas--;
    	}

    	int nfallos = 0; // Numero de intentos de asignacion de pasajeros
    	Random rand = new Random();
    	int con, posX, posY, pas;
    	
    	while ((nfallos < N) && (npas > 0)) {
    		// Seleccionamos a un conductor de forma aleatoria

    		con = rand.nextInt(K);
    		posX = registro[con][0];
    		posY = registro[con][1];
    		
    		//Escogemos a los pasajeros por proximidad con la posici�n actual,
    		//mientras sea posible
    		boolean rutaCompleta = false;
    		
    		while(!rutaCompleta) {
    			pas = pasMasProximo(posX, posY);
    			if (pas != -1 && asignarPasajero(con, pas)) {
        			//Actualizamos al posicion actual con la posicion final del pasajero
        			posX = registro[pas][2];
        			posY = registro[pas][3];
        		}
    			else rutaCompleta = true;
    		}
    		++nfallos;
    	}
    	
    	// Los conductores que no poseen ningun pasajero asignado dejan de serlo
    	for (int i = 0; i < K; i++)	{
    		if (((Vector<Integer>)conductores.get(i)).isEmpty()) {
    			eliminarConductor(i);
    		}
    	}
    }

    public void IAPracStateSolucionInicialB1()
    {	
    	
    	// Todos los Usuarios que pueden conducir pasan a ser conductores
    	ncond = K;
    	for (int i = 0; i < K; i++) {
    		conductores.add(new Vector<Integer>());
    		pasajerosPendientes.removeElement(i);
    		npas--;
    	}
    	

    	int nfallos = 0;  // Numero de intentos de asignacion de pasajeros
    	Random rand = new Random();
    	int con, posX, posY, pas;
    	
    	while ((nfallos < N) && (npas > 0) /*&& (npas > (N - K)/2)*/)	{
    		// Seleccionamos a un conductor de forma aleatoria
    		con = rand.nextInt(K);
    		posX = registro[con][0];
    		posY = registro[con][1];
    		
    		//Escogemos a los pasajeros por proximidad con la posicion actual,
    		//mientras sea posible
    		boolean rutaCompleta = false;
    		
    		while(!rutaCompleta) {
    			pas = pasMasProximo(posX, posY);
    			
    			if (pas != -1 && asignarPasajero(con, pas)) {
        			//Actualizamos al posicion actual con la posicion final del pasajero
        			posX = registro[pas][2];
        			posY = registro[pas][3];
        		}
    			else rutaCompleta = true;
    		}
    		++nfallos;
    	}
    }
    
    
    // Conjunto operadores
    public boolean asignarPasajero(int con, int pas) {
    	Vector<Integer> cruta = (Vector<Integer>)conductores.get(con);
		cruta.add(pas); // Recoger
		cruta.add(pas); // LLevar
		
		if (calculaDistRuta(con) <= MAX_HMSREC) {
			pasajerosPendientes.removeElement(pas);
			npas--;
			return true;
		}
		
		cruta.removeElement(pas);
		cruta.removeElement(pas);
		
		return false;
    }

    public boolean eliminarPasajero(int con, int pas) {
    	Vector<Integer> cruta = (Vector<Integer>)conductores.get(con);
  
    	if (cruta.removeElement(pas)) {
	        cruta.removeElement(pas);
	        pasajerosPendientes.add(pas);
	        npas++;
	        return true;
    	}
    	
    	return false;
    }
    
    public boolean moverPasajero(int con1, int pas, int con2) {
    	eliminarPasajero(con1, pas);
    	if (asignarPasajero(con2, pas)) return true;
    	asignarPasajero(con1, pas);
    	
    	return false;
    }
     
    // Operador Intercambiar contiguos
    public boolean switchPasajeros(int con, int pospas) {
    	Vector<Integer> cruta = (Vector<Integer>)conductores.get(con);
    	
    	if ((pospas >= 0) && (pospas < (cruta.size() - 1))) {
	    	int pas = ((Integer)cruta.get(pospas)).intValue();
	    	cruta.set(pospas, cruta.get(pospas + 1));
	    	cruta.set(pospas + 1, pas);
	    	
	    	if (calculaDistRuta(con) <= MAX_HMSREC && !plazasSuperadas(con)) return true;
	    	
	    	pas = ((Integer)cruta.get(pospas)).intValue();
	    	cruta.set(pospas, cruta.get(pospas + 1));
	    	cruta.set(pospas + 1, pas);
    	}
    	
    	return false;
    }
    
    // Operador Intercambiar
    public boolean switchPosicionesPasajeros(int con, int pos1, int pos2) {
    	Vector<Integer> cruta = (Vector<Integer>)conductores.get(con);
    	
    	if (pos1 != pos2) {
	    	int pas = ((Integer)cruta.get(pos1)).intValue();
	    	cruta.set(pos1, cruta.get(pos2));
	    	cruta.set(pos2, pas);
	    	
	    	if (calculaDistRuta(con) <= MAX_HMSREC && !plazasSuperadas(con)) return true;
	    	
	    	pas = ((Integer)cruta.get(pos1)).intValue();
	    	cruta.set(pos1, cruta.get(pos2));
	    	cruta.set(pos2, pas);
    	}
    	
    	return false;
    }

    public boolean eliminarConductor(int con) {
    	Vector<Integer> cruta = (Vector<Integer>)conductores.get(con);
		
    	if (cruta != null && cruta.size() == 0) {
			conductores.set(con, null);
			ncond--;
			pasajerosPendientes.add(con);
			npas++;
			return true;
    	}
    	
    	return false;
    }
    
    public boolean creaConductor(int con) {
    	if (conductores.get(con) == null) {
			conductores.add(con, new Vector<Integer>());
			pasajerosPendientes.removeElement(con);
			npas--;
			ncond++;
			return true;
    	}
		
    	return false;
    }
    
    // Consultoras
    public int getTotalHmsrec() {
    	int conDist = 0;
    	
    	for (int con = 0; con < K; con++) 
    	{
    		if(conductores.get(con) != null)
    			conDist += calculaDistRuta(con);
    	}
    	
    	return conDist;
    }
    
    public Vector<Vector<Integer>> getConductores() {
    	return conductores;
    }
    
    public Vector<Integer> getPasajerosPendientes() { 
    	return pasajerosPendientes; 
    }
    
    public boolean isGoalState() {
    	return false;
    }
    
    // Funciones auxliares
    public int calculaDistRuta(int con) {
    	Vector<Integer> rec = new Vector<Integer>();
    	Vector<Integer> cruta = (Vector<Integer>)conductores.get(con);
    	int nruta = cruta.size();
    	int dist = 0;
    	int posX = registro[con][0];
    	int posY = registro[con][1];
    	int pas;
    	
    	for (int i = 0; i < nruta; ++i) {
    		pas = ((Integer)cruta.get(i)).intValue();
    		if (rec.contains(pas)) {
    			dist += Math.abs(registro[pas][2] - posX) + Math.abs(registro[pas][3] - posY);
    			posX = registro[pas][2];
    			posY = registro[pas][3];
    		}
    		else {
    			rec.add(pas);
    			dist += Math.abs(registro[pas][0] - posX) + Math.abs(registro[pas][1] - posY);
    			posX = registro[pas][0];
    			posY = registro[pas][1];
    		}
    	}
    	
    	dist += Math.abs(registro[con][2] - posX) + Math.abs(registro[con][3] - posY);
    	
    	return dist;
    }
    
    private boolean plazasSuperadas(int con) {
    	Vector<Integer> rec = new Vector<Integer>();
    	Vector<Integer> cruta = (Vector<Integer>)conductores.get(con);
    	int nruta = cruta.size();
    	int nrec = 0;
    	
    	for (int i = 0; i < nruta; ++i) {
    		if (rec.contains(cruta.get(i))) --nrec;
    		else {
    			rec.add(i);
    			++nrec;
    		}
    		
    		if (nrec > MAX_PLAZASO) return false;
    	}
    	
    	return true;
    }    
    
    private int pasMasProximo(int posX, int posY) {
    	int pas = -1;
    	int pasmin = -1;
    	int distMin = MAX_HMSREC;
    	int dist;
    	
    	for(int i = 0; i < npas; i++) {
    		//Obtenemos al pasajero y calculamos la distancia para recogerlo
    		pas = ((Integer)pasajerosPendientes.get(i)).intValue();
    		dist = Math.abs(registro[i][0] - posX) + Math.abs(registro[i][1] - posY);
    		
    		//Si la nueva distancia es menor, actualizamos la distancia minima
    		// y el pasajero correspondiente
    		if(dist < distMin) {
    			distMin = dist;
    			pasmin = pas;
    		}
    	}
    	
    	return pasmin;
    }

    private Vector<Vector<Integer>> copiaConductores(Vector<Vector<Integer>> conds) {
    	Vector<Vector<Integer>> copia = new Vector<Vector<Integer>>();
    	Vector<Integer> ruta = null;
    	
    	for(int i = 0; i < K; i++) {
    		if(conds.get(i) != null) {
    			ruta = copiavectorInteger((Vector<Integer>)conds.get(i));
    		}
    		else ruta = null;
    		
    		copia.add(ruta);
    	}
    	
    	return copia;
    }
    
    private Vector<Integer> copiavectorInteger(Vector<Integer> v) {
    	Vector<Integer> copia = new Vector<Integer>();
    	int size = v.size();
    	
    	for(int i = 0; i < size; i++)
    		copia.add(new Integer(((Integer) v.get(i)).intValue()));
    	
    	return copia;
    }

    public void printConductores() {
    	Vector<Integer> cruta = null;
    	int nruta;
    	boolean first = true;
    	
    	for (int con = 0; con < K; con++) {
    		cruta = (Vector<Integer>)conductores.get(con);

    		if (cruta != null) {
	    		nruta = cruta.size();
	    		
	    		System.out.print(con + " : {");
	    		
	    		for (int j = 0; j < nruta; j++) {
	    			if (first) {
	    				System.out.print(cruta.get(j));
	    				first = false;
	    			}
	    			else System.out.print(", " + cruta.get(j));
	    		}
	    		
	    		System.out.println("}" + " (" + calculaDistRuta(con) + "hms)");
	    		first = true;
    		}
    	}
    }
    
    public void printRegistro()
    {
    	System.out.println("Registro de " + N + " usuarios");
    	
    	for(int us = 0; us < N; us++)
    		System.out.println(us + ": {(" + registro[us][0] + ", " + registro[us][1] + "), " +
    								   "(" + registro[us][2] + ", " + registro[us][3] + ")}");	
    }    
}

